#define _CRT_SECURE_NO_WARNINGS
#include<iostream>
#include<vector>
#include<string>
#include<numeric>
#include<unordered_map>
#include<algorithm>
using namespace std;
//class Djset
//{
//public:
//	vector<int> parent;
//	vector<int> rank;
//	Djset(int n)
//	{
//		parent.resize(n);
//		iota(parent.begin(), parent.end(), 0);
//		rank.resize(n);
//	}
//	int find(int x)
//	{
//		if (x != parent[x])
//		{
//			parent[x] = find(parent[x]);
//		}
//		return parent[x];
//	}
//	void merge(int x, int y)
//	{
//		int fx = find(x), fy = find(y);
//		if (fx == fy)
//			return;
//		if (rank[fx] < rank[fy])
//			swap(fx, fy);
//		parent[fy] = fx;
//		if (rank[fx] == rank[fy])
//			rank[fx]++;
//	}
//};
//string smallestStringWithSwaps(string s, vector<vector<int>>& pairs) {
//	int n = s.size();
//	Djset ds(n);
//	for (auto& v : pairs)
//	{
//		ds.merge(v[0], v[1]);
//	}
//	unordered_map<int, vector<int>> hash;
//	for (int i = 0; i < n; i++)
//	{
//		hash[ds.find(i)].push_back(i);
//	}
//	vector<char> ret(n);
//	for (auto& [k, v] : hash)
//	{
//		vector<int> tmp = v;
//		sort(tmp.begin(), tmp.end(), [&](int x,int y)
//			{
//				return s[x] < s[y];
//			});
//		for (int i = 0; i < v.size(); i++)
//		{
//			ret[v[i]] = s[tmp[i]];
//		}
//	}
//	string r;
//	for (auto& c : ret)
//		r += c;
//	return r;
//}
class Djset
{
public:
	vector<int> parent;
	Djset(int n)
	{
		parent.resize(n);
		iota(parent.begin(), parent.end(), 0);
	}
	int find(int x)
	{
		if (x != parent[x])
			parent[x] = find(parent[x]);
		return parent[x];
	}
	void merge(int x,int y)
	{
		int fx = find(x), fy = find(y);
		if (fx == fy)
			return;
		parent[fy] = fx;
	}
};
string smallestEquivalentString(string s1, string s2, string baseStr) {
	int n = s1.size();
	Djset ds(26);
	for (int i = 0; i < n; i++)
	{
		int x = s1[i] - 'a', y = s2[i] - 'a';
		ds.merge(x, y);
	}
	unordered_map<int, int> hash;
	for (int i = 0; i < 26; i++)
	{
		if (hash.count(ds.find(i)))
			hash[ds.find(i)] = min(hash[ds.find(i)], i);
		else
			hash[ds.find(i)] = i;
	}
	string ret;
	for (auto& c : baseStr)
	{
		int x = c - 'a';
		ret.push_back(hash[ds.find(x)] + 'a');
	}
	return ret;
}
int main()
{

	return 0;
}